package com.cherrish.demo.algorithm;

import com.cherrish.demo.algorithm.Algorithm;

/**
 * @author cherrish
 * @time 2019-01-18 10:51
 * @name AbstractAlgorithm
 * @desc:
 */
public abstract class AbstractAlgorithm implements Algorithm {
    protected static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    protected static void swap1(int[] arr, int x, int y){
        arr[x] = arr[x] + arr[y];
        arr[y] = arr[x] - arr[y];
        arr[x] = arr[x] - arr[y];
    }

    protected static void swap3(int[] arr, int x, int y){
        arr[x] = arr[x] ^ arr[y];
        arr[y] = arr[x] ^ arr[y];
        arr[x] = arr[x] ^ arr[y];
    }

    /**
     * 算法名称：计数基数排序
     * 算法描述：变长字符串的基数排序，使用in和out数组
     * 效果：如同字典中索引排序
     *
     * 复杂度分析：
     * 1.平均时间复杂度：
     * 2.空间复杂度：
     */
    protected static void countRadixSort(String[] arr, int strLen){
        final int BUCKETS = 256;
        int n = arr.length;
        String[] buffer = new String[n];
        String[] in = arr;
        String[] out = buffer;
        for(int pos = strLen -1; pos >= 0; pos--){
            int[] count = new int[BUCKETS + 1];
            for(int i = 0; i < n; i++){
                count[in[i].charAt(pos) + 1]++;
            }
            for(int b = 1; b < BUCKETS; b++){
                count[b] += count[b - 1];
            }
            for(int i = 0; i < n; i++){
                out[count[in[i].charAt(pos)]++] = in[i];
            }
            String[] temp = in;
            in = out;
            out = temp;
        }
        /**
         *  当字符串最长的长度是偶数，out最后引用的是a，排序结束
         *  当字符串最长的长度是奇数，需要把in复制至out
         */
        if(strLen % 2 == 1){
            for(int i = 0; i < arr.length; i++){
                out[i] = in[i];
            }
        }
    }
}
